#include <iostream>
#include <stack>
#include <vector>
 using namespace std;

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};
class Solution {
public:
	void ConvertList(TreeNode* root,TreeNode*& prev)
	{
		//搜索树的中序遍历就是有序的
		if(root==nullptr)
			return ;
		ConvertList(root->left,prev);
//核心是我们没法得知父节点 但我们知道子节点所以 我们让当前节点cur和子字节prev的链接起来
//再让子节点prev等于当前节点然后在递归回退的时候我们就拿到了cur的父节点了然后我们之前保存的cur
//就是现在prev 就是现在cur的子节点了 然后递归下去就链接好了
		TreeNode* cur = root;
		cur->left = prev;
		if(prev)
			prev->right = cur;

		prev = cur;
		ConvertList(root->right, prev);
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
		if(pRootOfTree==nullptr)
			return nullptr;
        TreeNode* prev = nullptr;
		ConvertList(pRootOfTree,prev); //这里的phea d指向的是根要让他指向头
		TreeNode* phead = pRootOfTree;
		while(phead->left)//因为要保证头节点是有效的所以phead->left不能为空
			phead = phead->left;
		return phead;
    }
};



// 递归过程中，需要一个变量prev记录 “上一个被访问的节点”（当前节点的前驱），通过以下步骤处理每个节点：
// 先递归遍历当前节点的左子树：确保左子树的节点先完成转换，为当前节点准备好前驱（左子树的最后一个节点）。
// 处理当前节点与前驱的双向关系：
// 当前节点的left指针指向prev（建立当前节点到前驱的左链接）；
// 若prev存在（非空），prev的right指针指向当前节点（建立前驱到当前节点的右链接），形成双向链表的基本单元。
// 更新prev为当前节点：因为接下来要遍历右子树，右子树的节点的前驱就是当前节点。
// 最后递归遍历当前节点的右子树：让右子树的节点以当前节点为前驱，继续建立链接。